package MyLinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description://这个模块主要进行链表代码的书写
 * 1、获取链表中的元素个数
 * 2、判断链表是否为空
 * 3、在链表头添加元素
 * 4、在链表中间添加元素
 * 5、在链表尾部添加元素
 * 6、设立虚拟头节点
 * 7、获取链表的第 index 个位置的元素
 * 8、修改链表的第 index 个位置的元素
 * 9、查找链表中是否有该元素
 * 10、删除链表的第 index 个位置的元素
 * 11、清空所有元素
 * User: 石方旭
 * Date: 2022-04-28
 * Time: 14:38
 */
public class MyLinkedList<E> {
//1、获取链表中的元素个数
//2、判断链表是否为空
    //创建一个节点
    private class ListNode{
        private E e;//数值域
        private ListNode next;//指针域

        public ListNode(E e,ListNode next) {
            this.e =e;
            this.next =null;
        }
        public ListNode(E e) {
            this(e,null);
        }
        public ListNode() {
            this(null,null);
        }
    }
    //创建一个虚拟的头结点
    public ListNode dummyHead;
    public int size;
    public MyLinkedList() {
        this.size =0;
        dummyHead = new ListNode();//虚拟头结点
    }
    //获取元素个数
    public int Size() {
        return size;
    }
    //判断链表是否为空
    public Boolean isEmpty() {
        return size==0;
    }
    //在链表index位置添加元素
    public void add(int index,E e){
        ListNode prev = dummyHead;
        //先找到index位置的前一个节点
        for(int i =0;i<index;++i) {
            prev = prev.next;
        }
        //此时已经找到了前一个节点
        ListNode node = new ListNode(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }
    //头插
    public void addFirst(E e) {
        add(0,e);
        size++;
    }
    //尾插
    public void addLast(E e) {
        add(Size()-1,e);
        size++;
    }
    //获取index位置的元素
    public E get(int index){
        ListNode cur = dummyHead;
        for(int i=0;i<=index;++i) {
            cur = cur.next;
        }
        return cur.e;
    }
    //设置index位置的元素
    public void set(int index,E e) {
        ListNode cur = dummyHead;
        for(int i =0;i<=index;++i) {
            cur = cur.next;
        }
        cur.e =e;
    }
    //查找链表中的元素
    public Boolean contains(E e) {
        ListNode cur = dummyHead.next;
        while(cur!=null) {
            if(cur.e==e){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //清空链表中的元素
    public void clear() {
        dummyHead=null;
        size=0;
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();

        ListNode cur = dummyHead.next;
        while(cur != null){
            res.append(cur.e + "->");
            cur = cur.next;
        }
        res.append("NULL");

        return res.toString();
    }
    //删除index下标的元素
    public void remove(int index) {
        //找到index位置前一个位置
        ListNode prev = dummyHead;
        for(int i =0;i<index;++i) {
            prev = prev.next;
        }
        //此时已经到达了要删除元素位置的前一个位置
        ListNode del = prev.next;
        prev.next = del.next;
        size--;
    }




}
